import java.util.ArrayList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=442 lang=java
 *
 * [442] 数组中重复的数据
 */

// @lc code=start
/*这里用来额外空间也过了。。。
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        List<Integer> resut=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                resut.add(nums[i]);
            }else{
                map.put(nums[i], 1);
            }
        }
        return resut;
    }
}
*/
//如果是相同的元素，那么以他们为索引的元素值一定是同一个值，因此可以修改该值来标记是否被访问过
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> resut=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            int index=Math.abs(nums[i])-1;//减一是为了确保index是数组下标范围
            if(nums[index]<0){//已经被访问过一次，才会变为负数
                resut.add(index+1);//对应的nums[i]=index+1
            }else{
                nums[index]*=-1;
            }
        }
        return resut;
    }
}
// @lc code=end

